
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1949. -- [Ceoi2006]Walk -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1949: [Ceoi2006]Walk</h2><span class=green>Time Limit: </span>4 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>162 MB<br><span class=green>Submit: </span>27&nbsp;&nbsp;<span class=green>Solved: </span>14<br>[<a href='submitpage.php?id=1949'>Submit</a>][<a href='problemstatus.php?id=1949'>Status</a>][<a href='bbs.php?id=1949'>Discuss</a>]</center><h2>Description</h2><div class=content>考虑X-Y平面上满足X≥0的整数结点

给定若干个矩形及一个目标点，紧靠每个矩形外部的一周范围内没有其它矩形的点，所有矩形中的所有点满足X≥0

求一条以(0,0)点为起点，以目标点为终点、不与任何矩形相交的最短路径</div><h2>Input</h2><div class=content>第一行输入为两个整数X与Y(1≤X≤106,-106≤Y≤106)表示目标点坐标

第二行为一个整数N(0≤N≤105)，表示矩形的数目

接下来的N行每行包括4个整数：
X1,Y1,X2,Y2(0≤X1,X2≤106,0≤Y1,Y2≤106)
即N个矩形的某对对角顶点。</div><h2>Output</h2><div class=content>第一行包括一个整数L，表示最短路径长度
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata>42 33<br />
66<br />
35 37 37 37<br />
13 -41 13 6<br />
40 -2 42 -1<br />
27 -2 28 -2<br />
15 -4 16 2<br />
29 16 29 16<br />
38 -34 38 -11<br />
22 -5 22 -5<br />
34 27 34 35<br />
28 12 29 12<br />
10 11 11 13<br />
11 25 11 25<br />
24 4 25 40<br />
27 9 27 10<br />
27 -4 27 -4<br />
29 7 29 10<br />
3 -13 5 -13<br />
16 17 16 17<br />
18 6 18 48<br />
4 7 4 14<br />
5 2 5 5<br />
40 22 44 32<br />
21 13 21 13<br />
34 3 34 25<br />
41 11 42 20<br />
15 -15 16 -9<br />
24 -46 25 -6<br />
5 -4 5 -3<br />
10 17 11 17<br />
28 14 29 14<br />
3 -15 4 -15<br />
10 15 10 15<br />
16 8 16 9<br />
2 2 2 2<br />
1 -4 3 -3<br />
10 21 10 21<br />
22 8 22 8<br />
20 -3 21 2<br />
10 19 11 19<br />
7 -47 8 3<br />
28 -11 28 -6<br />
20 4 20 9<br />
11 23 11 23<br />
15 -17 16 -17<br />
27 0 27 3<br />
43 5 43 8<br />
15 -7 16 -6<br />
16 -19 16 -19<br />
11 -10 11 -10<br />
21 11 22 11<br />
4 0 4 0<br />
15 5 16 6<br />
3 -11 5 -7<br />
11 -8 11 -1<br />
28 -13 28 -13<br />
21 15 22 15<br />
40 -30 43 -5<br />
41 34 43 35<br />
15 14 16 15<br />
21 -16 22 -13<br />
1 -1 2 -1<br />
10 1 11 9<br />
22 17 22 17<br />
31 -50 32 -1<br />
22 -8 22 -7<br />
16 -21 16 -21<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata>89<br />
</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=1949'>Submit</a>][<a href='problemstatus.php?id=1949'>Status</a>][<a href='bbs.php?id=1949'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
